package traverser;

/**
 * LIFO stack implementation
 */

import java.util.Iterator;
import java.util.NoSuchElementException;

public class Stack<Item> implements Iterable<Item> {
	LLNode head;
	int count;
	
	public Stack () {
		head = null;
		count = 0;
	}
	
	public void push (Item value) {
		LLNode node = new LLNode(value, head);
		head = node;
		count++;
	}
	
	public Item pop () {
		if (head == null) {
			return null;
		}
		count--;
		LLNode temp = head;
		head = temp.next;
		return temp.value;
	}
	
	public int count () {
		return count;
	}
	
	// Remove top and bottom values from the stack
	public Stack<Item> trim () {
		head = head.next;
		
		LLNode iter = head;
		LLNode prev = head;
		while (iter.next != null) {
			prev = iter;
			iter = iter.next;
		}
		prev.next = null;
		return this;
	}
	
	public void printStack() {
		System.out.println();
		LLNode temp = head;
		while (temp != null) {
			System.out.println(temp.value);
			temp = temp.next;
		}
		System.out.println();
	}
	
	public Iterator<Item> iterator () {
		return new LIFOiterator();
	}
	
	class LLNode {
		Item value;
		LLNode next;
		
		public LLNode (Item value, LLNode next) {
			this.value = value;
			this.next = next;
		}
	}
	
	class LIFOiterator implements Iterator<Item> {
		LLNode current = head;
		public boolean hasNext() {
			return current != null;
		}
		
		// We don't support remove, it doesn't make sense
		public void remove () {
			throw new UnsupportedOperationException();
		}
		
		public Item next() {
			if (!hasNext()) {
				throw new NoSuchElementException();
			}
			Item out = current.value;
			current = current.next;
			return out;
		}
	}

	public static void main (String [] args){
		Stack<Integer> test= new Stack<Integer>();
		test.push(1);
		test.push(2);
		test.push(3);
		test.push(4);
		test.push(5);
		test.push(6);
		test.push(7);
		test.push(8);
		test.push(9);
		test.printStack();
		System.out.println(test.pop());
		System.out.println(test.pop());
		System.out.println(test.pop());
		System.out.println(test.pop());
		test.printStack();
		System.out.println(test.pop());
		System.out.println(test.pop());
		System.out.println(test.pop());
		System.out.println(test.pop());
		System.out.println(test.pop());
		System.out.println(test.pop());
		System.out.println(test.pop());
		System.out.println(test.pop());
		System.out.println(test.pop());
		System.out.println(test.pop());
		System.out.println(test.pop());
		System.out.println(test.pop());
		System.out.println(test.pop());
		System.out.println(test.pop());
		test.push(10);
		test.push(11);
		test.push(12);
		test.push(13);
		System.out.println(test.pop());
		System.out.println(test.pop());
		System.out.println(test.pop());
		test.printStack();
		System.out.println(test.pop());
		System.out.println(test.pop());
		System.out.println(test.pop());
		System.out.println(test.pop());
		System.out.println(test.pop());
		System.out.println(test.pop());
		System.out.println(test.pop());
		System.out.println(test.pop());
		System.out.println(test.pop());
		System.out.println(test.pop());
		System.out.println(test.pop());
		test.push(1654);
		test.printStack();
	}
}
